package com.zdp.algorithm.stackandqueue;

import java.util.Stack;

/**
 * 逆序一个栈（使用递归 , 不使用额外空间)
 * @author Zhengdp
 * @date 2023年01月05日 11:33
 */
public class StackReverse {

    private static int[] elements = new int[]{
            1,2,3,4,5,6,7
    };
    public static void main(String[] args) {
      Stack<Integer> stack = new Stack<>();
      for(int element : elements) {
          stack.push(element);
      }
      reverse(stack);
      while(!stack.isEmpty()) {
          System.out.print(stack.pop() + " , ");
      }
    }

    /**
     * 弹出栈底元素（使用递归）
     * @param stack 栈
     * @return 栈底元素值
     * @param <T>
     */
    private static <T> T getLast(Stack<T> stack){
        T result = stack.pop();
        if(stack.isEmpty()) {
            // 当前元素为栈底元素，直接返回
            return result;
        } else {
            // 当前元素不为栈底元素，缩小stack范围，再次尝试获取栈底元素
            T last = getLast(stack);
            // 将非栈底元素重新压入栈中，因为是递归元素，所以压入元素的顺序与之前一致
            stack.push(result);
            return last;
        }
    }

    /**
     * 将栈倒置  （使用递归）
     * 将问题拆分 ： 弹出栈底元素 ， 倒置栈 ，将栈底元素 push到倒置后的栈
     * 递归终止条件： 当栈为空 (不需要倒置了) ==> 其实当栈中只有一个元素时就可以终止了
     * @param stack
     * @param <T>
     */
    private static <T> void reverse(Stack<T> stack) {
        if(stack.size() == 1) {
            return ;
        }
        T last = getLast(stack);
        reverse(stack);
        stack.push(last);
    }
}

